% Version control information:
%\svnid{$Id: voraz.tex 7 2009-04-20 22:10:35Z asalber $
%
\subsection{Técnica Voraz}
%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Técnica voraz}
La \textbf{técnica voraz} consiste en resolver un problema incrementalmente por etapas, tomando decisiones o realizando acciones que permiten ir construyendo progresivamente la solución del problema.

Normalmente se utiliza con problemas de optimización en los que hay que
buscar la solución óptima en un espacio de búsqueda que suele estructurarse en forma de árbol.

Con cada decisión tomada se obtiene una solución parcial del problema y se reduce la dimensionalidad del espacio de búsqueda mismo bajando un nivel en el mismo.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Condiciones necesarias para aplicar la téncnica voraz}
\begin{itemize}
\item Debe existir una función que hay que maximizar o minimizar conocida como \textbf{función objetivo}.
\item La función objetivo depende de varias variables que toman valores en un conjunto conocido como \textbf{dominio}. El dominio define un \textbf{espacio de búsqueda} que suele representarse en forma de árbol. La asignación de un valor a una variable se denomina \textbf{decisión} y supone dar un paso más en el espacio de búsqueda.
\item Existe una función, conocida como \textbf{función solución}, que permite saber si unos determinados valores de las variables son o no solución del problema.
\item Hay un conjunto de restricciones que deben satisfacer los valores de las variables de la función objetivo y existe una \textbf{función de factibilidad} para chequear si las decisiones tomadas hasta el momento satisfacen o no las restricciones.
\item El conjunto de decisiones factibles tomadas hasta el momento se llama \textbf{solución en curso}.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Funcionamiento de la técnica voraz}
La técnica voraz intenta resolver el problema por etapas, fijando progresivamente los valores de las variables de la función objetivo, sin violar las restricciones, hasta llegar al máximo o mínimo de dicha función.

En cada etapa se determina el valor de una de las variables aún no fijada mediante una \textbf{función de selección}. La función de selección siempre toma la decisión factible que es \emph{localmente óptima}, es decir, la que hace que la función objetivo tome el mejor valor posible hasta el momento, sin intentar averiguar si dicha decisión forma parte de la solución óptima global.

Una de las características que diferencian a la técnica voraz de otras que estudiaremos después es que \emph{\alert{¡nunca reconsidera una decisión tomada!}}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo genérico voráz}
Suponiendo que el dominio de las variables de la función objetivo fuese $c$, podemos expresar el algoritmo voraz así:
\begin{lstlisting}[mathescape]
funcion voraz(conjunto_candidatos $c$)
  $s=\emptyset$
  mientras(no solucion($s$) & no vacio($c$))
    $x$ = seleccion($c$)
    $c = c-\{x\}$ISO-8859-1
    si factible($s\cup\{x\}$) entonces $s = s\cup\{x\}$
  fin_mientrasISO-8859-1
  si solucion($s$) entonces devoler $s$
  si_no devolver $\emptyset$
fin_funcion
\end{lstlisting}
donde
\begin{itemize}
\item $c$ es el dominio del problema.
\item $s$ es es la solución en curso.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Coste temporal del algoritmo voraz}
El coste de un algoritmo voraz depende de dos factores:
\begin{itemize}
\item El n
... y ya estáúmero de iteraciones del bucle, que depende del tamaño de la solución construida y del tamaño del espacio de búsqueda.
\item El coste de las funciones selección y factible. La función factible suele tener un coste constante, pero la función selección ha de explorar el conjunto de candidatos y depende de su tamaño.
\end{itemize}
\end{frame}


\begin{frame}
\frametitle{Ventajas e inconvenientes de la técnica voraz}
La principal ventaja de los algoritmos voraces es que suelen ser bastante eficientes, precisamente por no reconsiderar las decisiones tomadas.

El principal inconveniente es que \emph{\alert{¡no garantizan la obtención de la solución óptima del problema!}}, ni siquiera que se obtenga una solución, aún cuando dicha solución exista. Esto es debido a que las decisiones localmente óptimas no garantizan la obtención de la solución óptima global.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Ejemplos de algoritmos voraces}
Algunos problemas conocidos que pueden resolverse mediante la técnica voraz son:
\begin{itemize}
\item El problema del cambio en monedas.
\item El problema de los códigos de Huffman.
\item El problema de los tiempos de espera mínimos.
\item El problema de la mochila.
\item El problema de los caminos mínimos en grafos.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Ejemplo de técnica voraz}
Dado un conjunto $M$ de monedas de $n$ tipos con valores $m_1,\ldots,m_n$, se
trata de encontrar el número mínimo de monedas que sumen una cantidad $x$.
\[
\includegraphics[scale=0.8]{img/monedas.eps} 
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema del cambio de monedas}
\framesubtitle{Funciones del algoritmo voraz}
\begin{itemize}
\item \textbf{Función objetivo}: El número de monedas, que hay que minimizar.
\item \textbf{Dominio o conjunto de candidatos}: El conjunto $M$ formado por
todas las monedas de que disponemos.
\item \textbf{Función solución}: $S=\{m_1,\ldots,m_k\}$ es solución si $\sum_i
m_i = x$.
\item \textbf{Función factible}: $S=\{m_1,\ldots,m_k\}$ es factible si $\sum_i
m_i \leq x$.
\item \textbf{Función selección}: Elegir si es posible la moneda de mayor valor
de $M$.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema del cambio de monedas}
\framesubtitle{Ejemplo de técnica voraz}
El siguiente algoritmo implementado en Java utiliza la técnica voraz para resolver el problema del cambio de monedas:
\begin{lstlisting}
public boolean cambio(int x, int n, int[] valor, int[] solucion){
  for (int i=0; i<n; i++) solucion[i] = 0;
  int i = 0, suma = 0;
  while (suma < x && i < n)
    if (suma + valor[i] <= x){
      solucion[i]++;
      suma += valor[i];}
    else
      i++;
  if (suma == x) return true;
  else return false;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Optimalidad del problema del cambio de monedas}
\framesubtitle{Ejemplo de técnica voraz}
El algoritmo anterior no siempre proporciona la solución óptima.

\textbf{Ejemplo}. Si tenemos 5 monedas de valores \texttt{valor[5]={50,25,20,5,1}} y  queremos sumar \texttt{x=42}, el algoritmo nos daría la solución \texttt{s[5]={0,1,0,3,2}}, es decir, 6 monedas, mientras que la solución óptima es  \texttt{s[5]={0,0,2,0,2}}, que son 4 monedas.

Además, en caso de que $M$ no contenga la moneda unidad, ni siquiera se
garantiza que el problema tenga la solución.

Para que el algoritmo alcance la solución óptima es necesario que $M$ esté
formado por tipos de monedas que sean potencia de un tipo básico $t$ (por ejemplo, \texttt{C={125,25,5,1}}). En este caso, el problema se reduce a encontrar la descomposición de $x$ en base $t$, que es única y mínima.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Coste del problema del cambio de monedas}
\framesubtitle{Ejemplo de técnica voraz}
Para que la función de selección de la función \texttt{cambio} funcione adecuadamente, el vector de valores de las monedas debe estar ordenado en orden decreciente.
 
El coste de este algoritmo es de $O(max(nlog n, m))$ donde $n$ es el número de
tipos de monedas de $M$, y $m$ es el número de iteraciones que realiza el bucle.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila}
\framesubtitle{Ejemplo de técnica voraz}
Se dispone de una colección de $n$ objetos $o_1,\ldots,o_n$, cada uno de ellos con un peso $p_i$ y un valor $v_i$ asociados y una mochila capaz de soportar un peso máximo $p_{max}$.

El problema consiste en maximizar el valor de los objetos que se introduzcan en la mochila sin sobrepasar $p_{max}$.

Dependiendo de si los objetos se pueden fraccionar o no, existen dos variantes del problema:
\begin{description}
\item[Mochila fraccionada:] Los objetos se pueden fraccionar, es decir se puede colocar en la mochila trozos de objetos.
\item[Mochila entera:] Los objetos no se pueden fraccionar y por tanto deben ir enteros en la mochila.
\end{description}
Sólo el primero puede resolverse con la técnica voraz.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila fraccionada}
\framesubtitle{Elementos de la técnica voraz}
Puesto que los objetos se pueden fraccionar, llamaremos $x_i$ al la fracción del objeto $o_i$ que colocamos en la mochila.
\begin{itemize}
\item \textbf{Función objetivo}: El valor de los objetos introducidos en la mochila $\sum_i x_iv_i$, que hay que maximizar.
\item \textbf{Dominio}: La colección de objetos $C$ que queremos introducir en la mochila.
\item \textbf{Función solución}: $S=\{x_1,\ldots,x_k\}$ es solución si $\sum_i x_ip_i = p_{max}$.
\item \textbf{Función factible}: $S=\{x_1,\ldots,x_k\}$ es factible si $\sum_i x_ip_i \leq p_{max}$.
\item \textbf{Función selección}: Existen varias estrategias posibles:
\begin{itemize}
\item Seleccionar los objetos en orden decreciente de valor.
\item Seleccionar los objetos en orden creciente de peso.
\item Seleccionar los objetos por orden decreciente de relación valor/peso. (Sólo esta conduce a la solución óptima).
\end{itemize}
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{El problema de la mochila fraccionada}
\framesubtitle{Ejemplo de la técnica voraz}
El siguiente algoritmo implementado en Java utiliza la técnica voraz para resolver el problema de la mochila fraccionaria:
\begin{lstlisting}
// mochilavoraz.java
public double mochila(objeto[] o, double pesomax) {
  double peso=0, valor=0;
  double []sol = new double[o.length];
  int i=0;
  while (peso<pesomax && i<o.length){
    if (peso+o[i].peso<=pesomax){ //El objeto cabe en la mochila
      sol[i] = 1;
      valor += o[i].valor;
      peso += o[i].peso;
    } 
    else { //El objeto no cabe en la mochila
      sol[i] = (pesomax-peso) / o[i].peso;
      valor += o[i].valor * sol[i];
      peso = pesomax;
    }
    i++;
  }
  return valor;
}   
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{El problema de la mochila fraccionada}
\framesubtitle{Coste temporal}
\begin{itemize}
\item El tamaño del problema es el número de objetos $n$.
\item El primer bucle realiza $n$ iteraciones y el coste de su cuerpo es constante, de modo que el coste total del bucle es $O(n)$. 
\item El coste de la función de ordenación decreciente de los objetos por valor/peso es el coste del algoritmo de ordenación utilizado (suele ser $O(n log n)$).
\item El segundo bucle realiza, a lo sumo $n$ iteraciones, y el coste de su cuerpo es constante, de manera que el coste total del bucle también es $O(n)$.
\end{itemize}
Por tanto, el coste total del algoritmo es 
\[
O(n) + O(n \log n) + O(n) = O(n \log n).
\]
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Árbol de recubrimiento mínimo de un grafo}

Dado un grafo conexo y no dirigido, un
\emph{árbol de recubrimiento} del grafo es un subgrafo que es un árbol y
conecta todos los vértices del grafo. Si las aristas del grafo tienen asignados
pesos, el peso del árbol de recubrimiento es la suma de los pesos de sus
aristas. El \emph{árbol de recubrimiento mínimo} del grafo es el árbol de
recubrimiento con el menor peso.

%% Adjacency matrix of graph
%% \  a  b  c  d  e  f  g
%% a  x  7     5
%% b  7  x  8  9  7
%% c     8  x     5
%% d  5  9     x 15  6
%% e     7  5 15  x  8  9
%% f           6  8  x 11
%% g              9  11 x

\begin{center}
\begin{pspicture}(0,0)(6,4.5)
{\psset{fillstyle=solid,fillcolor=orange}
\cnodeput(0,4){A}{$A$}
\cnodeput(2,4){B}{$B$}
\cnodeput(6,4){C}{$C$}
\cnodeput(0,2){D}{$D$}
\cnodeput(4,2){E}{$E$}
\cnodeput(2,0){F}{$F$}
\cnodeput(6,0){G}{$G$}
}
\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{-}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc[green]{A}{B}{7}
\arc[green]{A}{D}{5}
\arc{B}{C}{8}
\arc{B}{D}{9}
\arc[green]{B}{E}{7}
\arc[green]{C}{E}{5}
\arc{D}{E}{15}
\arc[green]{D}{F}{6}
\arc{E}{F}{8}
\arc[green]{E}{G}{9}
\arc{F}{G}{11}
\end{pspicture}
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda voraz del árbol de recubrimiento mínimo}
Según se represente el espacio de búsqueda del árbol de recubrimiento mínimo,
existen distintas estragtegias para construirlo:
\begin{itemize}
\item \textbf{Selección de vértices}: El árbol se construye añadiendo vértices
progresivamente. En cada etapa la función de selección toma el siguiente
vértice localmente óptimo aún no seleccionado.\\
El algoritmo más conocido de este tipo es el \emph{algoritmo de Prim}.
\item \textbf{Selección de aristas}: El árbol se construye añadiendo aristas
progresivamente. En cada etapa la función de selección toma la siguiente arista
localmente óptima aún no seleccionada.\\
El algoritmo más conocido de este tipo esl el \emph{algoritmo de Kruskal}.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo de Prim}
\framesubtitle{Funciones del algoritmo voraz}
Sea $G=\langle V,A\rangle$ un grafo conexo y no dirigido, donde $V$ es el
conjunto de vértices y $A$ el de aristas.

El algoritmo de Prim va construyendo el árbol de recubrimiento partiendo de un
vértice cualquiera y añadiendo nuevos vértices al árbol.

\begin{itemize}
\item \textbf{Función objetivo}: Minimizar el peso del árbol de recubrimiento.
\item \textbf{Dominio o conjunto de candidatos}: El conjunto $V$ formado por
todos los vértices del grafo.
\item \textbf{Función solución}: $S=\{v_1,\ldots,v_k\}$ es solución si
 se han añadido ya todos los vértices, es decir, $S=V$.
\item \textbf{Función factible}: No hay restricciones. 
\item \textbf{Función selección}: En cada etapa, elegir el vértice más cercano
al árbol construido.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo de Prim}
\framesubtitle{Ejemplo}
\begin{columns}
\begin{column}{0.5\linewidth}
Matriz de adyacencia del grafo
\begin{center}
\scalebox{0.8}{
\begin{tabular}{|c|ccccccc|}
\hline 
Dist  & A & B & C & D & E & F & G\\
\hline
A &   & 7 &   & 5 &   &   & \\
B & 7 &   & 8 & 9 & 7 &   & \\
C &   & 8 &   & 5 &   &   &  \\
D & 5 & 9 &   &   & 15 & 6 & \\
E &   & 7 & 5 & 15 &   & 8 & 9\\
F &   &   &   &  6 & 8 &   & 11\\
G &   &   &   &    & 9 & 11 & \\
\hline
\end{tabular}
}
\end{center}

\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(6,4.5)
{\psset{fillstyle=solid,fillcolor=orange}
\cnodeput(0,4){A}{$A$}
\cnodeput(2,4){B}{$B$}
\cnodeput(6,4){C}{$C$}
\cnodeput(0,2){D}{$D$}
\cnodeput(4,2){E}{$E$}
\cnodeput(2,0){F}{$F$}
\cnodeput(6,0){G}{$G$}
}
\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{-}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc{A}{B}{7}
\arc{A}{D}{5}
\arc{B}{C}{8}
\arc{B}{D}{9}
\arc{B}{E}{7}
\arc{C}{E}{5}
\arc{D}{E}{15}
\arc{D}{F}{6}
\arc{E}{F}{8}
\arc{E}{G}{9}
\arc{F}{G}{11}

\psset{fillstyle=solid,fillcolor=green}
\uncover<2->{\cnodeput(0,2){D}{$D$}}
\uncover<3->{\cnodeput(0,4){A}{$A$}}
\uncover<4->{\cnodeput(2,0){F}{$F$}}
\uncover<5->{\cnodeput(2,4){B}{$B$}}
\uncover<6->{\cnodeput(4,2){E}{$E$}}
\uncover<7->{\cnodeput(6,4){C}{$C$}}
\uncover<8->{\cnodeput(6,0){G}{$G$}}

\uncover<3->{\arc[green]{A}{D}{5}}
\uncover<4->{\arc[green]{D}{F}{6}}
\uncover<5->{\arc[green]{A}{B}{7}}
\uncover<6->{\arc[green]{B}{E}{7}}
\uncover<7->{\arc[green]{C}{E}{5}}
\uncover<8->{\arc[green]{E}{G}{9}}
\end{pspicture}
}
\end{center}
\end{column}
\begin{column}{0.45\linewidth}
Pasos del algoritmo:
\scriptsize
\begin{enumerate}
  \item<2-> $S=\{D,\}$, $V=\{A,B,C,E,F,G\}$,
  $\mbox{distancia}=\{5,9,\infty,0,15,6,\infty\}$,
  $\mbox{verticemin}=\{D,D,D,D,D,D,D\}$
  \item<3-> $S=\{D,A\}$, $V=\{B,C,E,F,G\}$,
  $\mbox{distancia}=\{0,7,\infty,0,15,6,\infty\}$,
  $\mbox{verticemin}=\{D,A,D,D,D,D,D\}$
  \item<4-> $S=\{D,A,F\}$, $V=\{B,C,E,G\}$, 
  $\mbox{distancia}=\{0,7,\infty,0,8,0,11\}$,
  $\mbox{verticemin}=\{D,A,D,D,F,D,F\}$
  \item<5-> $S=\{D,A,F,B\}$, $V=\{C,E,G\}$, $\mbox{distancia}=\{0,0,8,0,7,0,11\}$,
  $\mbox{verticemin}=\{D,A,B,D,B,D,F\}$
  \item<6-> $S=\{D,A,F,B,E\}$, $V=\{C,G\}$, $\mbox{distancia}=\{0,0,5,0,0,0,9\}$,
  $\mbox{verticemin}=\{D,A,E,D,B,D,E\}$
  \item<7-> $S=\{D,A,F,B,E,C\}$, $V=\{G\}$, $\mbox{distancia}=\{0,0,0,0,0,0,9\}$,
  $\mbox{verticemin}=\{D,A,E,D,B,D,E\}$
  \item<8-> $S=\{D,A,F,B,E,C,G\}$, $V=\emptyset$, $\mbox{distancia}=\{0,0,0,0,0,0,0\}$,
  $\mbox{verticemin}=\{D,A,E,D,B,D,E\}$
\end{enumerate}
\end{column}
\end{columns}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de Prim}
\framesubtitle{Implementación}
\begin{lstlisting}
public Grafo Prim(Grafo g) {
  int n = g.numVertices();
  Grafo arbol = new Grafo(n);
  // Distancias minimas de cada vertice no seleccionado al arbol
  float distancia[] = new float[n];
  //Vertice del arbol mas cercano a cada vertice no seleccionado
  int verticemin[] = new int[n];
  // Comenzamos con un arbol con el primer vertice.
  // Una distancia 0 indica que el vertice ya se ha incluido
  distancia[0] = 0;  
  // Inicalmente las distancias de cada vertice al arbol son 
  // las de las aristas que los unen al primer vertice
  for(int i=1; i<n; i++){
    distancia[i] = g.peso(0, i);
    verticemin[i] = 0;
  }
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de Prim}
\framesubtitle{Implementación (continuación)}
\begin{lstlisting}
  // Comienza el bucle voraz
  for(int i=1; i<n; i++){
    float min = Float.MAX_VALUE;
    int jmin = 0;
    // Buscamos el siguiente vertice mas cercano al arbol.
    for(int j=1; j<n; j++)
      if (distancia[j]>0 && distancia[j]<min){
        min = distmin[j];
        jmin = j;
      }
    // Incluimos en el arbol el vertice mas cercano.
    distancia[jmin] = 0;
    arbol.addArista(verticemin[jmin],jmin,
                    g.peso(verticemin[jmin],jmin));
    //Actualizamos las distancias al arbol de los demas vertices
    for(int j=1; j<n; j++)
      if (g.peso(jmin,j)<distancia[j]){
        distancia[j] = g.peso(jmin,j);
        verticemin[j] = jmin;
      }
  }
return arbol;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Complejidad del algoritmo de Prim}
Si $n$ es el número de vértices del grafo y $m$ el número de aristas, entonces
tenemos que el coste temporal del algoritmo es $O(n^2)$ ya que el bucle voraz
realiza $n$ iteraciones y en su cuerpo hay otros bucles que también realizan $n$
iteraciones.

No obstante, usando una lista de adyacencia para representar las aristas del
grafo, y estructuras más eficientes para representar las distancias, se puede
conseguir un coste temporal $O(m+n\log n)$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo de Kruskal}
\framesubtitle{Funciones del algoritmo voraz}
Sea $G=\langle V,A\rangle$ un grafo conexo y no dirigido, donde $V$ es el
conjunto de vértices y $A$ el de aristas.

El algoritmo de Kruskal va construyendo el árbol de recubrimiento partiendo de
un árbol sin aristas y añadiendo progresivamente aristas de $A$.

\begin{itemize}
\item \textbf{Función objetivo}: Minimizar el peso del árbol de recubrimiento.
\item \textbf{Dominio o conjunto de candidatos}: El conjunto $A$ formado por
todas las aristas del grafo.
\item \textbf{Función solución}: $S=\{a_1,\ldots,a_k\}$ es solución si
 se han añadido tantas aristas como vértices tenga el grafo menos una, es decir,
 $|S|=|V|-1$.
\item \textbf{Función factible}: Las aristas seleccionadas no pueden formar
ciclos.
\item \textbf{Función selección}: En cada etapa, elegir la arista de menor peso
aún no seleccionada, que no forme ciclo con las ya seleccionadas.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo de Kruskal}
\framesubtitle{Ejemplo}
\begin{columns}
\begin{column}{0.5\linewidth}
Matriz de adyacencia del grafo
\begin{center}
\scalebox{0.8}{
\begin{tabular}{|c|ccccccc|}
\hline 
Dist  & A & B & C & D & E & F & G\\
\hline
A &   & 7 &   & 5 &   &   & \\
B & 7 &   & 8 & 9 & 7 &   & \\
C &   & 8 &   & 5 &   &   &  \\
D & 5 & 9 &   &   & 15 & 6 & \\
E &   & 7 & 5 & 15 &   & 8 & 9\\
F &   &   &   &  6 & 8 &   & 11\\
G &   &   &   &    & 9 & 11 & \\
\hline
\end{tabular}
}
\end{center}
\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(6,4.5)
\cnodeput[fillstyle=solid,fillcolor=green](0,4){A}{$A$}
\cnodeput[fillstyle=solid,fillcolor=cyan](2,4){B}{$B$}
\cnodeput[fillstyle=solid,fillcolor=orange](6,4){C}{$C$}
\cnodeput[fillstyle=solid,fillcolor=red](0,2){D}{$D$}
\cnodeput[fillstyle=solid,fillcolor=blue](4,2){E}{$E$}
\cnodeput[fillstyle=solid,fillcolor=yellow](2,0){F}{$F$}
\cnodeput[fillstyle=solid,fillcolor=magenta](6,0){G}{$G$}

\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{-}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc{A}{B}{7}
\arc{A}{D}{5}
\arc{B}{C}{8}
\arc{B}{D}{9}
\arc{B}{E}{7}
\arc{C}{E}{5}
\arc{D}{E}{15}
\arc{D}{F}{6}
\arc{E}{F}{8}
\arc{E}{G}{9}
\arc{F}{G}{11}

\psset{fillstyle=solid,fillcolor=green}
\uncover<3->{\arc[green]{A}{D}{5}
\cnodeput[fillstyle=solid,fillcolor=green](0,2){D}{$D$}} 
\uncover<4->{\arc[orange]{C}{E}{5}
\cnodeput[fillstyle=solid,fillcolor=orange](4,2){E}{$E$}}
\uncover<5->{\arc[green]{D}{F}{6}
\cnodeput[fillstyle=solid,fillcolor=green](2,0){F}{$F$}}
\uncover<6->{\arc[cyan]{B}{E}{7}
\arc[cyan]{C}{E}{5}
\cnodeput[fillstyle=solid,fillcolor=cyan](4,2){E}{$E$}
\cnodeput[fillstyle=solid,fillcolor=cyan](6,4){C}{$C$}}
\uncover<7->{\arc[green]{A}{B}{7}
\arc[green]{C}{E}{5}
\cnodeput[fillstyle=solid,fillcolor=green](4,2){E}{$E$}
\arc[green]{B}{E}{7}
\cnodeput[fillstyle=solid,fillcolor=green](2,4){B}{$B$}
\cnodeput[fillstyle=solid,fillcolor=green](6,4){C}{$C$}}
\uncover<8->{\arc[green]{E}{G}{9}
\cnodeput[fillstyle=solid,fillcolor=green](6,0){G}{$G$}}
\end{pspicture}
}
\end{center}
\end{column}
\begin{column}{0.45\linewidth}
Pasos del algoritmo:
\scriptsize
\begin{enumerate}
  \item<2-> $S=\{\}$\\ $\mbox{bosque}=\{A,B,C,D,E,F,G\}$
  \item<3-> $S=\{(A,D)\}$\\ $\mbox{bosque}=\{A,B,C,A,E,F,G\}$
  \item<4-> $S=\{(A,D),(C,E)\}$\\ $\mbox{bosque}=\{A,B,C,A,C,F,G\}$
  \item<5-> $S=\{(A,D),(C,E),(D,F)\}$\\ $\mbox{bosque}=\{A,B,C,A,C,A,G\}$
  \item<6-> $S=\{(A,D),(C,E),(D,F),(B,E)\}$\\ $\mbox{bosque}=\{A,B,B,A,B,A,G\}$
  \item<7-> $S=\{(A,D),(C,E),(D,F),(B,E),(A,B)\}$\\ $\mbox{bosque}=\{A,A,A,A,A,A,G\}$
  \item<8-> $S=\{(A,D),(C,E),(D,F),$\\ $(B,E),(A,B),(E,G)\}$\\
  $\mbox{bosque}=\{A,A,A,A,A,A,A\}$
\end{enumerate}
\end{column}
\end{columns}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de Kruskal}
\framesubtitle{Implementación}
\begin{lstlisting}
public Grafo Kruskal(Grafo g, PriorityQueue<Arista> c) {
// Las aristas de c estan ordenadas de menor a mayor peso
  int n = g.numVertices();
  Grafo arbol = new Grafo(n);
  // Incialmente cada vertice forma un arbol
  int bosque[] = new int[n]; 
  for (int i=0; i<n; i++) bosque[i] = i;
  // Comienza el bucle voraz	
  int i = 1;
  while (!c.isEmpty() && i<n){
    Arista e = q.poll();
    // Si la arista no forma un ciclo la incluimos en el arbol
    if (forest[e.origen()] != forest[e.destino()]){
      arbol.addArista(e);
      i++;
      // Unimos los arboles que conecta la arista
      for (int j=0; j<n; j++)
        if (bosque[j]==bosque[e.destino()]) 
          bosque[j] = bosque[e.origen()];
    }
  }
return arbol; 
}   
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Complejidad del algoritmo de Kruskal}
Si $n$ es el número de vértices del grafo y $m$ el número de aristas, entonces
tenemos:
\begin{itemize}
  \item La ordenación de las aristas por menor peso tiene coste $O(m\log m)$.
  \item El bucle voraz tiene un coste de $O(n^2)$.
\end{itemize}
Así pues el coste temporal del algoritmo es $O(n^2)$ pero con una estructura
más eficiente para representar el bosque se puede conseguir un orden $O(m\log
m)$.
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[label=caminos_minimos]
\frametitle{Camínos mínimos en un grafo}

Sea $G=\langel V,A\rangle$ un grafo dirigido con pesos en sus aristas.
Llamaremos \emph{camino} del vértice $v_o$ al vértice $v_d$ de $V$,
al un conjunto de aristas
\[
C(v_o,v_d)=\{(v_0,v_1),(v_1,v_2),\ldots,(v_{k-1},v_k)\},
\]
tal que $v_0 = v_o$,
$v_k=v_d$. 

El \emph{peso de un camino} es la suma de los pesos de las aristas
que lo conforman. 

Diremos que un camino $C(v_o,v_d)$ es \emph{mínimo} o de \emph{peso mínimo} si
es el camino de meno peso de todos los posibles caminos de $v_o$ a $v_d$.

\begin{center}
\scalebox{0.75}{
\begin{pspicture}(0,0)(6,4.5)
{\psset{fillstyle=solid,fillcolor=orange}
\cnodeput(0,4){A}{$A$}
\cnodeput(2,4){B}{$B$}
\cnodeput(6,4){C}{$C$}
\cnodeput(0,2){D}{$D$}
\cnodeput(4,2){E}{$E$}
\cnodeput(2,0){F}{$F$}
\cnodeput(6,0){G}{$G$}
}
\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{->}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc{A}{B}{3}
\arc{B}{E}{7}
\arc{C}{B}{8}
\arc{D}{A}{5}
\arc{D}{B}{9}
\arc[green]{D}{F}{6}
\arc[green]{E}{C}{5}
\arc{E}{D}{15}
\arc{E}{G}{9}
\arc[green]{F}{E}{8}
\arc{F}{G}{11}
\arc{G}{C}{3}
\end{pspicture}
}

Camino mínimo del vértice $D$ al vértice $C$. Su peso es 19.
\end{center}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Búsqueda de caminos mínimos: Algoritmo de Dijkstra}
El objetivo ahora es calcular el camino mínimo de un vértice dado al resto de
los vértices.

Sea $G=\langle V,A\rangle$ un grafo conexo y dirigido, donde $V$ es el
conjunto de vértices y $A$ el de aristas.

El algoritmo de Dijkstra utiliza una estrategia similar al algoritmo de Prim.
En cada etapa del algoritmo voraz se calcula la distancia mínima al siguiente
vértice más cercano. 

\begin{itemize}
\item \textbf{Función objetivo}: Minimizar el peso del camino del vértice dado
a los demás.
\item \textbf{Dominio o conjunto de candidatos}: El conjunto $V$ formado por
todos los vértices del grafo.
\item \textbf{Función solución}: $S=\{v_1,\ldots,v_k\}$ es solución si
 se han añadido ya todos los vértices, es decir, $S=V$.
\item \textbf{Función factible}: No hay restricciones. 
\item \textbf{Función selección}: En cada etapa, elegir el vértice más cercano
aún no seleccionado.
\end{itemize}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Algoritmo de Dijkstra}
\framesubtitle{Ejemplo}
\begin{columns}
\begin{column}{0.5\linewidth}
Matriz de adyacencia del grafo
\begin{center}
\scalebox{0.8}{
\begin{tabular}{|c|ccccccc|}
\hline 
Dist  & A & B & C & D & E & F & G\\
\hline
A &   & 3 &   &   &   &   & \\
B &   &   &   &   & 7 &   & \\
C &   & 8 &   &   &   &   &  \\
D & 5 & 9 &   &   &   & 6 & \\
E &   &   & 5 & 15 &   &  & 9\\
F &   &   &   &   & 8 &   & 11\\
G &   &   & 3 &   &   &   & \\
\hline
\end{tabular}
}
\end{center}

\begin{center}
\scalebox{0.8}{
\begin{pspicture}(0,0)(6,4.5)
{\psset{fillstyle=solid,fillcolor=orange}
\cnodeput(0,4){A}{$A$}
\cnodeput(2,4){B}{$B$}
\cnodeput(6,4){C}{$C$}
\cnodeput(0,2){D}{$D$}
\cnodeput(4,2){E}{$E$}
\cnodeput(2,0){F}{$F$}
\cnodeput(6,0){G}{$G$}
}
\newcommand\arc[4][black]{%
    \ncline[linecolor=#1]{->}{#2}{#3}
    \ncput{\colorbox{white}{#4}}
}
\arc{A}{B}{3}
\arc{B}{E}{7}
\arc{C}{B}{8}
\arc{D}{A}{5}
\arc{D}{B}{9}
\arc{D}{F}{6}
\arc{E}{C}{5}
\arc{E}{D}{15}
\arc{E}{G}{9}
\arc{F}{E}{8}
\arc{F}{G}{11}
\arc{G}{C}{3}

\psset{fillstyle=solid,fillcolor=green}
\uncover<2->{\cnodeput(0,2){D}{$D$}}
\uncover<3->{\cnodeput(0,4){A}{$A$}}
\uncover<4->{\cnodeput(2,0){F}{$F$}}
\uncover<5->{\cnodeput(2,4){B}{$B$}}
\uncover<6->{\cnodeput(4,2){E}{$E$}}
\uncover<7->{\cnodeput(6,4){C}{$C$}}
\uncover<8->{\cnodeput(6,0){G}{$G$}}

\uncover<3->{\arc[green]{A}{D}{5}}
\uncover<4->{\arc[green]{D}{F}{6}}
\uncover<5->{\arc[green]{A}{B}{7}}
\uncover<6->{\arc[green]{B}{E}{7}}
\uncover<7->{\arc[green]{C}{E}{5}}
\uncover<8->{\arc[green]{E}{G}{9}}
\end{pspicture}
}
\end{center}
\end{column}
\begin{column}{0.45\linewidth}
Pasos del algoritmo:
\scriptsize
\begin{enumerate}
  \item<2-> Vértice de origen $D$\\ $S=\{D,\}$, $V=\{A,B,C,E,F,G\}$,
  $\mbox{distancia}=\{5,9,\infty,0,\infty,6,\infty\}$, $\mbox{antecesor}=\{D,D,D,D,D,D,D\}$
  \item<3-> $S=\{D,A\}$, $V=\{B,C,E,F,G\}$,
  $\mbox{distancia}=\{5,8,\infty,0,\infty,6,\infty\}$, $\mbox{antecesor}=\{D,A,D,D,D,D,D\}$
  \item<4-> $S=\{D,A,F\}$, $V=\{B,C,E,G\}$, 
  $\mbox{distancia}=\{5,8,\infty,0,14,6,17\}$, $\mbox{antecesor}=\{D,A,D,D,F,D,F\}$
  \item<5-> $S=\{D,A,F,B\}$, $V=\{C,E,G\}$, 
  $\mbox{distancia}=\{5,8,\infty,0,14,6,17\}$, $\mbox{antecesor}=\{D,A,D,D,B,D,F\}$
  \item<6-> $S=\{D,A,F,B,E\}$, $V=\{C,G\}$, 
  $\mbox{distancia}=\{5,8,19,0,14,6,17\}$, $\mbox{antecesor}=\{D,A,E,D,B,D,F\}$
  \item<7-> $S=\{D,A,F,B,E,G\}$, $V=\{C\}$, 
  $\mbox{distancia}=\{5,8,19,0,14,6,17\}$, $\mbox{antecesor}=\{D,A,E,D,B,D,F\}$
  \item<8-> $S=\{D,A,F,B,E,C,G\}$, $V=\emptyset$, 
  $\mbox{distancia}=\{5,8,19,0,14,6,17\}$, $\mbox{antecesor}=\{D,A,E,D,B,D,F\}$
\end{enumerate}
\end{column}
\end{columns}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de Dijkstra}
\framesubtitle{Implementación}
\begin{lstlisting}
public int[] Dijkstra(Graph g, int inicio) {	
  int n = g.numVertices();
  // Distancias minimas a cada vertice no seleccionado
  float distmin[] = new float[n];
  // Vertice antecesor en el camino minimo
  int antecesor[] = new int[n];
  // Vertices para los que ya se ha calculado el camino minimo
  boolean calculado[] = new boolean[n];
  // Inicializamos las distancias minimas de cada vertice a la 
  // distancia de las aristas directas con el vertice de origen
  for(int i=0; i<n; i++){
    distancia[i] = g.peso(inicio, i);
    antecesor[i] = inicio;
    calculado[i] = false;
  }
  // La distancia del vertice inicial a si mismo es 0
  distancia[inicio]] = 0;
  calculado[inicio] = true;
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}[containsverbatim]
\frametitle{Algoritmo de Dijkstra}
\framesubtitle{Implementación (continuación)}
\begin{lstlisting}
  // Bucle voraz 
  for(int i=1; i<n; i++){
    float min = Float.MAX_VALUE;
    int jmin=0;
    // Buscamos el siguiente vertice mas cercano
    for(int j=0; j<n; j++)
      if (!calculado[j] && distancia[j]<min){
        min = distancia[j];
        jmin = j;
      }
    // Marcamos el vertice como calculado
    calculado[jmin] = true;  
    //Actualizamos las distancias minimas del resto de vertices
    for(int j=0; j<n; j++)
      if (!calculado[j] && 
          distancia[j]>distancia[jmin]+g.peso(jmin,j)){
        distancia[j] = distancia[jmin]+g.peso(jmin,j);
        antecesor[j] = jmin;
      }
  }
return antecesor;
}
\end{lstlisting}
\end{frame}


%---------------------------------------------------------------------slide----
\begin{frame}
\frametitle{Complejidad del algoritmo de Dijkstra}
Si $n$ es el número de vértices del grafo y $m$ el número de aristas, entonces
el coste temporal del algoritmo es $O(n^2)$ ya que el bucle voraz realiza $n$
iteraciones y en su cuerpo hay otros bucles que también realizan $n$
iteraciones.

No obstante, usando una lista de adyacencia para representar las aristas del
grafo, y estructuras más eficientes para representar las distancias, se puede
conseguir un coste temporal $O(m+n\log n)$.
\end{frame}

